// STL
#include <algorithm>                // std::sort()
#include <utility>                  // std::pair<>, ::make_pair()
#include <vector>                   // std::vector<>


//
// DESC: Estimate the cumulative distribution function (CDF) of the probability distribution from which a set of data was drawn.
//
// -----
//
// NOTE: S_N(x) is an unbiased estimator.
//
inline std::pair<
                 std::vector<double>, // CDF_x
                 std::vector<double>  // CDF_y
                 > distribution::CDF(
                                     const std::vector<double> &data
                                     )
{
    std::vector<double> CDF_x;
    std::vector<double> CDF_y;

    // SORT x (ASCENDING)
    CDF_x = data;
    std::sort(CDF_x.begin(), CDF_x.end());

    // CALCULATE WEIGHT OF EACH POINT
    double w = 1./CDF_x.size();

    for( auto i = 0; i < CDF_x.size(); ++i )
    {
        // NOTE: The CDF of X, evaluated at x, is the probability that X will take a value less than *or equal to* x.
        //
        // NOTE: ... (Hence the inclusion of this point.)

        if( i != 0 )
        {
            // CHECK IF WE'RE AT THE SAME x
            if( CDF_x[i] == CDF_x[i-1] )
            {
                CDF_y.back() += w;

                CDF_x.erase( (CDF_x.begin()+i) );

                --i;
            }
            // ... ELSE ADD A NEW POINT
            else
            {
                CDF_y.push_back( (CDF_y.back() + w) );
            }
        }
        else
        {
            CDF_y.push_back( w );
        }
    }

    return std::make_pair(
                          CDF_x,
                          CDF_y
                          );
}
